/*
 * Saphre - Suffix Arrays for Phrase Extraction
 * Copyright (C) 2013 
 * Dale Gerdemann - Tübingen, Germany 
 * Niko Schenk - Frankfurt am Main, Germany
 * All rights reserved.
 *
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 *
 */
package util;

import java.io.Serializable;

/**
 * Implements a kind of binary search over intervals.
 * 
 * @author Dale Gerdemann
 */
public class IntervalSearch implements Serializable {

    private static final int INIT_SIZE = 8;
    public int[] lo;        // low value of interval
    public int[] hi;        // high value of interval
    int N = 0;       // number of intervals

    /**
     * 
     * @return 
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < N; i++) {
            Interval inter = new Interval(lo[i], hi[i]);
            sb.append(inter);
            sb.append(",");
        }
        sb.setCharAt(sb.length() - 1, ']');
        return sb.toString();
    }

    public IntervalSearch() {
        this(INIT_SIZE);
    }

    public IntervalSearch(int initCapacity) {
        lo = new int[initCapacity];
        hi = new int[initCapacity];
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    
    /**
     * double the size of the arrays
     * @param SIZE 
     */
    private void resize(int SIZE) {
        int[] tempLo = new int[SIZE];
        int[] tempHi = new int[SIZE];
        for (int i = 0; i < N; i++) {
            tempHi[i] = hi[i];
        }
        for (int i = 0; i < N; i++) {
            tempLo[i] = lo[i];
        }
        hi = tempHi;
        lo = tempLo;
    }

    
    /**
     * Add interval, assumed to be non-overlapping so no error checking
     * @param newLo
     * @param newHi 
     */
    public void put(int newLo, int newHi) {
        if (N >= lo.length) {
            resize(2 * N);
        }

        // shift lo-hi pairs one position to right, and add new
        // lo-hi pair, This loop can be eliminated since lo-hi
        // pairs are always added in order anyway.
        int i = N;
        while ((i > 0) && (newLo < hi[i - 1])) {
            lo[i] = lo[i - 1];
            hi[i] = hi[i - 1];
            i--;
        }
        lo[i] = newLo;
        hi[i] = newHi;
        N++;
    }

    /**
     * return Interval associated with given key, or a dummy Interval
     * if no such key
     * @param key
     * @return 
     */
    public Interval get(int key) {
        int i = bsearch(key);
        if (i == -1) {
            return new Interval(0, -1);
        }
        return new Interval(lo[i], hi[i]);
    }

    
    /**
     * binary search in interval [left, right]
     * @param key
     * @return 
     */
    public int bsearch(int key) {
        int left = 0, right = N - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (lo[mid] <= key && key <= hi[mid]) {
                return mid;
            }
            if (key < lo[mid]) {
                right = mid - 1;
            } else if (key > hi[mid]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    public int[] lo() {
        return lo;
    }

    public int[] hi() {
        return hi;
    }

    
    /**
     * Test routine.
     * @param args 
     */
    public static void main(String[] args) {
        IntervalSearch st = new IntervalSearch();

        st.put(1643, 2033);
        st.put(5532, 7643);
        st.put(8999, 10332);
        st.put(5666653, 5669321);
        System.out.println(st.get(9122));
        System.out.println(st.get(8122));
    }
}
